{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #随机链表的复制"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: copyRandomList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #复杂链表的复制"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>请实现 <code>copyRandomList</code> 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 <code>next</code> 指针指向下一个节点，还有一个 <code>random</code> 指针指向链表中的任意节点或者 <code>null</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e1.png\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>head = [[7,null],[13,0],[11,4],[10,2],[1,0]]\n",
    "<strong>输出：</strong>[[7,null],[13,0],[11,4],[10,2],[1,0]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e2.png\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>head = [[1,1],[2,1]]\n",
    "<strong>输出：</strong>[[1,1],[2,1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e3.png\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>head = [[3,null],[3,0],[3,null]]\n",
    "<strong>输出：</strong>[[3,null],[3,0],[3,null]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>head = []\n",
    "<strong>输出：</strong>[]\n",
    "<strong>解释：</strong>给定的链表为空（空指针），因此返回 null。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>-10000 &lt;= Node.val &lt;= 10000</code></li>\n",
    "\t<li><code>Node.random</code>&nbsp;为空（null）或指向链表中的节点。</li>\n",
    "\t<li>节点数目不超过 1000 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题与主站 138 题相同：<a href=\"https://leetcode-cn.com/problems/copy-list-with-random-pointer/\">https://leetcode-cn.com/problems/copy-list-with-random-pointer/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [fu-za-lian-biao-de-fu-zhi-lcof](https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [fu-za-lian-biao-de-fu-zhi-lcof](https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[7,null],[13,0],[11,4],[10,2],[1,0]]', '[[1,1],[2,1]]', '[[3,null],[3,0],[3,null]]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        nums = []\n",
    "        cur = head\n",
    "        mapping = {}\n",
    "        idx = 0\n",
    "        while(cur):\n",
    "            nums.append(cur.val)\n",
    "            mapping[cur] = idx \n",
    "            cur = cur.next \n",
    "            idx += 1\n",
    "        random_idx = []\n",
    "        cur = head \n",
    "        while(cur):\n",
    "            if(cur.random == None):\n",
    "                random_idx.append(None)\n",
    "            else:\n",
    "                random_idx.append(mapping[cur.random])\n",
    "            cur = cur.next\n",
    "        h = Node(x=-1)\n",
    "        p = h\n",
    "        random_node = []\n",
    "        for num in nums:\n",
    "            p.next = Node(x=num)\n",
    "            p = p.next \n",
    "            random_node.append(p)\n",
    "        h = h.next \n",
    "        c = h\n",
    "        for i in range(len(random_node)):\n",
    "            if(random_idx[i] == None):\n",
    "                c.random = None \n",
    "            else:\n",
    "                c.random = random_node[random_idx[i]]\n",
    "            c = c.next \n",
    "        return h\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: return\n",
    "        hmap = {}\n",
    "        # 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射\n",
    "        cur = head\n",
    "        while cur:\n",
    "            hmap[cur] = Node(cur.val)\n",
    "            cur = cur.next\n",
    "        cur = head\n",
    "        # 4. 构建新节点的 next 和 random 指向\n",
    "        while cur:\n",
    "            hmap[cur].next = hmap.get(cur.next)\n",
    "            hmap[cur].random = hmap.get(cur.random)\n",
    "            cur = cur.next\n",
    "        # 5. 返回新链表的头节点\n",
    "        return hmap[head]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    ns = {}\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return None\n",
    "\n",
    "        if head not in self.ns:\n",
    "            node = Node(head.val)\n",
    "            self.ns[head] = node\n",
    "            node.next = self.copyRandomList(head.next)\n",
    "            node.random = self.copyRandomList(head.random)\n",
    "\n",
    "        return self.ns[head] \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: return\n",
    "        hmap = {}\n",
    "        # 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射\n",
    "        cur = head\n",
    "        while cur:\n",
    "            hmap[cur] = Node(cur.val)\n",
    "            cur = cur.next\n",
    "        cur = head\n",
    "        # 4. 构建新节点的 next 和 random 指向\n",
    "        while cur:\n",
    "            hmap[cur].next = hmap.get(cur.next)\n",
    "            hmap[cur].random = hmap.get(cur.random)\n",
    "            cur = cur.next\n",
    "        # 5. 返回新链表的头节点\n",
    "        return hmap[head]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return None\n",
    "        cur = head\n",
    "        dict = {}\n",
    "        while cur:\n",
    "            dict[cur] = Node(cur.val)\n",
    "            cur = cur.next\n",
    "        cur = head\n",
    "        while cur:\n",
    "            dict[cur].next = dict.get(cur.next)\n",
    "            dict[cur].random = dict.get(cur.random)\n",
    "            cur = cur.next\n",
    "        return dict[head]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:return\n",
    "        hmap={}\n",
    "        cur=head\n",
    "        while cur:\n",
    "            hmap[cur]=Node(cur.val)\n",
    "            cur=cur.next\n",
    "        cur=head\n",
    "        while cur:\n",
    "            hmap[cur].next=hmap.get(cur.next)\n",
    "            hmap[cur].random=hmap.get(cur.random)\n",
    "            cur=cur.next\n",
    "        return hmap[head]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        # dummy = Node(-1)\n",
    "        # current = dummy\n",
    "        # while head:\n",
    "        #     current.next = Node(head.val)\n",
    "        #     current.random = head.random\n",
    "        #     current.next = head.next\n",
    "        #     current = current.next\n",
    "        #     head = head.next\n",
    "        # return dummy.next        \n",
    "\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        # Create a mapping from original node to its copy\n",
    "        mapping = {}\n",
    "        \n",
    "        # Create a new linked list without setting the random pointers\n",
    "        dummy = Node(-1)\n",
    "        current = dummy\n",
    "        original = head\n",
    "        while original:\n",
    "            new_node = Node(original.val)\n",
    "            mapping[original] = new_node\n",
    "            current.next = new_node\n",
    "            current = new_node\n",
    "            original = original.next\n",
    "        \n",
    "        # Set the random pointers for the new linked list using the mapping\n",
    "        original = head\n",
    "        current = dummy.next\n",
    "        while original:\n",
    "            if original.random:\n",
    "                current.random = mapping[original.random]\n",
    "            original = original.next\n",
    "            current = current.next\n",
    "        \n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: return\n",
    "        hmap = {}\n",
    "        # 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射\n",
    "        cur = head\n",
    "        while cur:\n",
    "            hmap[cur] = Node(cur.val)\n",
    "            cur = cur.next\n",
    "        cur = head\n",
    "        # 4. 构建新节点的 next 和 random 指向\n",
    "        while cur:\n",
    "            hmap[cur].next = hmap.get(cur.next)\n",
    "            hmap[cur].random = hmap.get(cur.random)\n",
    "            cur = cur.next\n",
    "        # 5. 返回新链表的头节点\n",
    "        return hmap[head]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if head == None:return None\n",
    "        ans = Node(0)\n",
    "        p = head\n",
    "        while p:\n",
    "            newnode = Node(p.val,p.next)\n",
    "            p.next = newnode\n",
    "            p = newnode.next\n",
    "\n",
    "        p,q,cur = head,head.next,ans\n",
    "        while q:\n",
    "            q.random = p.random.next if p.random != None else None\n",
    "            cur.next = q\n",
    "            cur = cur.next\n",
    "            p = q.next\n",
    "            if p != None:\n",
    "                q = p.next\n",
    "            else:\n",
    "                break\n",
    "             \n",
    "        \n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        cur = head\n",
    "        hmap = {}\n",
    "        while cur:\n",
    "            hmap[cur] = Node(cur.val)\n",
    "            cur = cur.next\n",
    "\n",
    "        cur = head\n",
    "        while cur:\n",
    "            hmap[cur].next = hmap.get(cur.next)\n",
    "            hmap[cur].random = hmap.get(cur.random)\n",
    "            cur = cur.next\n",
    "\n",
    "        return hmap.get(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: return\n",
    "        m = dict()\n",
    "        cur = head \n",
    "        while cur:\n",
    "            m[cur] = Node(cur.val)\n",
    "            cur = cur.next \n",
    "        \n",
    "        cur = head\n",
    "        while cur:\n",
    "            m[cur].next = m.get(cur.next)\n",
    "            m[cur].random = m.get(cur.random)\n",
    "            cur = cur.next\n",
    "        \n",
    "        return m[head]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: return\n",
    "        hmap = {}\n",
    "        cur = head\n",
    "        while cur:\n",
    "            hmap[cur] = Node(cur.val)\n",
    "            cur = cur.next\n",
    "        cur = head\n",
    "        while cur:\n",
    "            hmap[cur].next = hmap.get(cur.next)\n",
    "            hmap[cur].random = hmap.get(cur.random)\n",
    "            cur = cur.next\n",
    "        return hmap[head]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:return \n",
    "        h = {}\n",
    "        cur = head\n",
    "        while cur:\n",
    "            h[cur] = Node(cur.val)\n",
    "            cur = cur.next\n",
    "        cur = head\n",
    "        while cur:\n",
    "            h[cur].next = h.get(cur.next)\n",
    "            h[cur].random = h.get(cur.random)\n",
    "            cur = cur.next\n",
    "        return h[head]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head):\n",
    "        if not head:\n",
    "            return\n",
    "        cur = head\n",
    "        while cur:\n",
    "            tmp = Node(cur.val)\n",
    "            tmp.next = cur.next\n",
    "            cur.next = tmp\n",
    "            cur = tmp.next\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.random:\n",
    "                cur.next.random = cur.random.next\n",
    "            cur = cur.next.next\n",
    "        cur = res = head.next\n",
    "        while cur.next:\n",
    "            cur.next = cur.next.next\n",
    "            cur = cur.next\n",
    "        cur.next = None\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: return \n",
    "        hmap = {}\n",
    "        cur = head\n",
    "        while cur:\n",
    "            hmap[cur] = Node(cur.val)\n",
    "            cur = cur.next\n",
    "        cur=head\n",
    "        while cur:\n",
    "            hmap[cur].next = hmap.get(cur.next)\n",
    "            hmap[cur].random = hmap.get(cur.random)\n",
    "            cur = cur.next\n",
    "        return hmap[head]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        nodes = []\n",
    "        hash = dict()\n",
    "        cur = head\n",
    "        while cur:\n",
    "            node = Node(cur.val)\n",
    "            hash[cur] = node\n",
    "            nodes.append(node)\n",
    "            cur = cur.next\n",
    "        nodes.append(None)\n",
    "        cur, i = head, 0\n",
    "        while cur:\n",
    "            nodes[i].next = nodes[i+1]\n",
    "            nodes[i].random = hash[cur.random] if cur.random else None\n",
    "            cur = cur.next\n",
    "            i += 1\n",
    "        return nodes[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return\n",
    "        \n",
    "        # 既然要进行深拷贝，并且还有随机指针，那么我们可以用hash_table:\n",
    "        hash_table = {}\n",
    "        cur = head\n",
    "        \n",
    "        while cur:\n",
    "            hash_table[cur] = Node(cur.val)\n",
    "            cur = cur.next\n",
    "        cur = head\n",
    "\n",
    "        while cur:\n",
    "            hash_table[cur].next = hash_table.get(cur.next)\n",
    "            hash_table[cur].random = hash_table.get(cur.random)\n",
    "            cur = cur.next\n",
    "        return hash_table[head]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if(head==None):\n",
    "            return None\n",
    "        dic = {}\n",
    "        cur = head\n",
    "        while(cur):\n",
    "            dic[cur] = Node(cur.val)\n",
    "            cur = cur.next\n",
    "        cur = head\n",
    "        while(cur):\n",
    "            dic[cur].next = dic.get(cur.next)\n",
    "            dic[cur].random = dic.get(cur.random)\n",
    "            cur = cur.next\n",
    "        return dic[head]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: return\n",
    "        cur=head\n",
    "        while cur:\n",
    "            tmp=Node(cur.val)\n",
    "            tmp.next=cur.next\n",
    "            cur.next=tmp\n",
    "            cur=tmp.next\n",
    "        cur=head\n",
    "        while cur:\n",
    "            if cur.random:\n",
    "                cur.next.random=cur.random.next\n",
    "            cur=cur.next.next\n",
    "        cur=head\n",
    "        pre=res=cur.next\n",
    "        while pre.next:\n",
    "            cur.next=cur.next.next\n",
    "            pre.next=pre.next.next\n",
    "            cur=cur.next\n",
    "            pre=pre.next\n",
    "        cur.next=None\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        # first-pass copy val\n",
    "        cur = head\n",
    "        while cur:\n",
    "            copy = Node(cur.val)\n",
    "            copy.next = cur.next\n",
    "            cur.next = copy\n",
    "            cur = cur.next.next\n",
    "        # second-pass copy random\n",
    "        cur = head\n",
    "        nxt = cur.next\n",
    "        while cur:\n",
    "            nxt.random = cur.random.next if cur.random else None\n",
    "            cur = cur.next.next\n",
    "            if cur:\n",
    "                nxt = nxt.next.next\n",
    "        # seperate two lists\n",
    "        cur = head\n",
    "        nxt = cur.next\n",
    "        ret = nxt\n",
    "        while cur:\n",
    "            cur.next = cur.next.next\n",
    "            cur = cur.next\n",
    "            if cur:\n",
    "                nxt.next = nxt.next.next\n",
    "                nxt = nxt.next\n",
    "        return ret\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return\n",
    "        \n",
    "        old_to_new = {}\n",
    "        cur = head\n",
    "        while cur:\n",
    "            old_to_new[cur] = Node(cur.val, None, None)\n",
    "            cur = cur.next\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.random:\n",
    "                old_to_new[cur].random = old_to_new[cur.random]\n",
    "            if cur.next:\n",
    "                old_to_new[cur].next = old_to_new[cur.next]\n",
    "            cur = cur.next\n",
    "            \n",
    "        return old_to_new[head]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        hmap=dict()\n",
    "        cur=head\n",
    "        while cur:\n",
    "            hmap[cur]=Node(cur.val)\n",
    "            cur=cur.next\n",
    "        cur=head\n",
    "        while cur:\n",
    "            if cur.next in hmap:\n",
    "                hmap[cur].next=hmap[cur.next]\n",
    "            if cur.random in hmap:\n",
    "                hmap[cur].random=hmap[cur.random]\n",
    "            cur=cur.next\n",
    "\n",
    "        return hmap[head]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not head:\n",
    "            return\n",
    "        dic={}\n",
    "        cur=head\n",
    "        #复制各节点\n",
    "        while cur:\n",
    "            dic[cur]=Node(cur.val)\n",
    "            cur=cur.next\n",
    "        cur=head\n",
    "        #构建next，random\n",
    "        while cur :\n",
    "            dic[cur].next=dic.get(cur.next)\n",
    "            dic[cur].random=dic.get(cur.random)\n",
    "            cur=cur.next\n",
    "        return  dic[head]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: return\n",
    "        has = {}\n",
    "        current = head\n",
    "        while current:\n",
    "            has[current] = Node(current.val)\n",
    "            current = current.next\n",
    "        \n",
    "        current = head\n",
    "        while current:\n",
    "            has[current].next = has.get(current.next)\n",
    "            has[current].random = has.get(current.random)\n",
    "            current = current.next\n",
    "        \n",
    "        return has[head]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not head:\n",
    "            return\n",
    "        dic={}\n",
    "        cur=head\n",
    "        #复制各节点\n",
    "        while cur:\n",
    "            dic[cur]=Node(cur.val)\n",
    "            cur=cur.next\n",
    "        cur=head\n",
    "        #构建next，random\n",
    "        while cur :\n",
    "            dic[cur].next=dic.get(cur.next)\n",
    "            dic[cur].random=dic.get(cur.random)\n",
    "            cur=cur.next\n",
    "        return  dic[head]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: \n",
    "            return\n",
    "        hmap = {}\n",
    "        cur = head\n",
    "        while cur:\n",
    "            hmap[cur] = Node(cur.val)\n",
    "            cur = cur.next\n",
    "\n",
    "        cur = head\n",
    "        while cur:\n",
    "            hmap[cur].next = hmap.get(cur.next)\n",
    "            hmap[cur].random = hmap.get(cur.random)\n",
    "            cur = cur.next\n",
    "            \n",
    "        return hmap[head]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: return\n",
    "        has = {}\n",
    "        current = head\n",
    "        while current:\n",
    "            has[current] = Node(current.val)\n",
    "            current = current.next\n",
    "        \n",
    "        current = head\n",
    "        while current:\n",
    "            has[current].next = has.get(current.next)\n",
    "            has[current].random = has.get(current.random)\n",
    "            current = current.next\n",
    "        \n",
    "        return has[head]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: \n",
    "            return head\n",
    "            \n",
    "        nodeDict = {}\n",
    "        cur = head\n",
    "        while cur:\n",
    "            nodeDict[cur] = Node(cur.val)\n",
    "            cur = cur.next\n",
    "        \n",
    "        cur = head\n",
    "        while cur:\n",
    "            nodeDict[cur].next = nodeDict.get(cur.next)\n",
    "            nodeDict[cur].random = nodeDict.get(cur.random)\n",
    "            cur = cur.next\n",
    "        \n",
    "        return nodeDict[head]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        upos=dict()\n",
    "        nodelist=[]\n",
    "        cur=head\n",
    "        index=0\n",
    "        while cur:\n",
    "            new_node=Node(cur.val)\n",
    "            nodelist.append(new_node)\n",
    "            upos[cur]=index\n",
    "            index+=1\n",
    "            cur=cur.next\n",
    "        # 串起来\n",
    "        for i in range(1,len(nodelist)):\n",
    "            nodelist[i-1].next=nodelist[i]\n",
    "        # 串起来\n",
    "        cur=head\n",
    "        while cur:\n",
    "            if cur.random:\n",
    "                nodelist[upos[cur]].random=nodelist[upos[cur.random]]\n",
    "            cur=cur.next\n",
    "        return nodelist[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: return\n",
    "        cur = head\n",
    "        while cur:\n",
    "            tmp = Node(cur.val)\n",
    "            tmp.next = cur.next\n",
    "            cur.next = tmp\n",
    "            cur = tmp.next\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.random:\n",
    "                cur.next.random = cur.random.next\n",
    "            cur = cur.next.next\n",
    "        cur = res = head.next\n",
    "        pre = head\n",
    "        while cur.next:\n",
    "            pre.next = pre.next.next\n",
    "            cur.next = cur.next.next\n",
    "            pre = pre.next\n",
    "            cur = cur.next\n",
    "        pre.next = None\n",
    "        return res    \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: return\n",
    "        has = {}\n",
    "        current = head\n",
    "        while current:\n",
    "            has[current] = Node(current.val)\n",
    "            current = current.next\n",
    "        \n",
    "        current = head\n",
    "        while current:\n",
    "            has[current].next = has.get(current.next)\n",
    "            has[current].random = has.get(current.random)\n",
    "            current = current.next\n",
    "        \n",
    "        return has[head]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return\n",
    "        hamp = dict()\n",
    "        cur = head\n",
    "        while cur:\n",
    "            hamp[cur] = Node(cur.val)\n",
    "            cur = cur.next\n",
    "        cur = head\n",
    "        while cur:\n",
    "            hamp[cur].next = hamp.get(cur.next)\n",
    "            hamp[cur].random = hamp.get(cur.random)\n",
    "            cur = cur.next\n",
    "        return hamp[head]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: return\n",
    "        hmap = {}\n",
    "        cur = head\n",
    "        while cur:\n",
    "            hmap[cur] = Node(cur.val)\n",
    "            cur = cur.next\n",
    "        cur = head\n",
    "        while cur:\n",
    "            hmap[cur].next = hmap.get(cur.next)\n",
    "            hmap[cur].random = hmap.get(cur.random)\n",
    "            cur = cur.next\n",
    "        return hmap[head]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: return head\n",
    "        cur=head\n",
    "        while cur:\n",
    "            tmp=Node(cur.val)\n",
    "            tmp.next=cur.next\n",
    "            cur.next=tmp\n",
    "            cur=tmp.next\n",
    "        cur=head\n",
    "        while cur:\n",
    "            if cur.random:\n",
    "                cur.next.random=cur.random.next\n",
    "            cur=cur.next.next\n",
    "        cur=tmp=head.next\n",
    "        pre=head\n",
    "        while cur.next:\n",
    "            pre.next=pre.next.next\n",
    "            cur.next=cur.next.next\n",
    "            pre=pre.next\n",
    "            cur=cur.next\n",
    "        pre.next=None\n",
    "        return tmp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:return \n",
    "        cur = head\n",
    "        while cur:\n",
    "            tmp = Node(cur.val)\n",
    "            tmp.next = cur.next\n",
    "            cur.next = tmp\n",
    "            cur = tmp.next\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.random:\n",
    "                cur.next.random = cur.random.next\n",
    "            cur = cur.next.next\n",
    "        cur = res = head.next\n",
    "        pre = head\n",
    "        while cur.next:\n",
    "            pre.next = pre.next.next\n",
    "            cur.next = cur.next.next\n",
    "            pre = pre.next\n",
    "            cur = cur.next\n",
    "        pre.next = None\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return None\n",
    "        map = {}\n",
    "        point = head\n",
    "        while point:\n",
    "            map[point] = Node(point.val)\n",
    "            point = point.next\n",
    "        cur = head\n",
    "        while cur:\n",
    "            map[cur].next = map.get(cur.next)\n",
    "            map[cur].random = map.get(cur.random)\n",
    "            cur = cur.next\n",
    "        return map[head]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "\n",
    "        map = {}\n",
    "        cur = head\n",
    "        while cur is not None:\n",
    "            map[cur] = Node(cur.val)\n",
    "            cur = cur.next\n",
    "        cur = head\n",
    "        while cur:\n",
    "            map[cur].next = map.get(cur.next)\n",
    "            map[cur].random = map.get(cur.random)\n",
    "            cur = cur.next\n",
    "        return map[head]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if head==None:\n",
    "            return None\n",
    "        Nodelist2=[]\n",
    "        Nodelist=[]\n",
    "        Nodelist.append(head)\n",
    "        p=head\n",
    "        new_head=Node(p.val)\n",
    "        p2=new_head\n",
    "        p=p.next\n",
    "        while(p!=None):\n",
    "            p2.next=Node(p.val) \n",
    "            Nodelist.append(p)\n",
    "            Nodelist2.append(p2)\n",
    "\n",
    "            p2=p2.next\n",
    "            p=p.next\n",
    "        p2.next=None\n",
    "        Nodelist2.append(p2)\n",
    "        p=head\n",
    "        p2=new_head\n",
    "       \n",
    "       # print(Nodelist)\n",
    "        while(p!=None):\n",
    "            if  not p.random in Nodelist :\n",
    "                p2.random=None\n",
    "            else:\n",
    "                idx=Nodelist.index(p.random)\n",
    "                p2.random=Nodelist2[idx]\n",
    "            p=p.next\n",
    "            p2=p2.next\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        p=head\n",
    "        ans=None\n",
    "        tail=None\n",
    "        node_dict=defaultdict(Node)\n",
    "\n",
    "        while p!=None:\n",
    "            if ans==None:\n",
    "                ans=Node(p.val)\n",
    "                node_dict[p]=ans\n",
    "                tail=ans\n",
    "            else:\n",
    "                tail.next=Node(p.val)\n",
    "                tail=tail.next\n",
    "                node_dict[p]=tail\n",
    "            p=p.next\n",
    "        p1=head\n",
    "        p2=ans\n",
    "        while p1!=None:\n",
    "            if p1.random!=None and p1.random in node_dict:\n",
    "                p2.random=node_dict[p1.random]\n",
    "            p1=p1.next\n",
    "            p2=p2.next\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if head == None: return \n",
    "        cur = head\n",
    "        \n",
    "        # A->B => A->A'->B->B'\n",
    "        # 复制val和next\n",
    "        while cur:\n",
    "            tmp = Node(cur.val)\n",
    "            tmp.next = cur.next\n",
    "            cur.next = tmp\n",
    "            cur = tmp.next\n",
    "        # 复制random\n",
    "        cur = head\n",
    "        while cur:\n",
    "            # 原random节点不为空\n",
    "            if cur.random:\n",
    "                # 重连random节点\n",
    "                cur.next.random = cur.random.next\n",
    "            cur = cur.next.next\n",
    "        pre = head\n",
    "        cur = head.next\n",
    "        res = cur\n",
    "        # 还原 A->A'->B->B' => A'->B'\n",
    "        while cur.next:\n",
    "            pre.next = pre.next.next\n",
    "            cur.next = cur.next.next\n",
    "            pre = pre.next\n",
    "            cur = cur.next\n",
    "        pre.next = None\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        h1 = head\n",
    "        h2 = head\n",
    "        vals = []\n",
    "        while h1:\n",
    "            vals.append(h1.val)\n",
    "            h1 = h1.next\n",
    "        vals.append(h1)\n",
    "        random_node = []\n",
    "        for i in range(len(vals)-1):\n",
    "            r_node = h2.random\n",
    "            cut = 0\n",
    "            while r_node:\n",
    "                cut = cut + 1\n",
    "                r_node = r_node.next\n",
    "            random_node.append(len(vals)-1-cut)\n",
    "            h2 = h2.next\n",
    "        node_list = []\n",
    "        for i in range(len(vals)-1):\n",
    "            node_list.append(Node(vals[i]))\n",
    "        node_list.append(None)\n",
    "        for i in range(len(node_list)-1):\n",
    "            node_list[i].next = node_list[i+1]\n",
    "            node_list[i].random = node_list[random_node[i]]\n",
    "        return node_list[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "import copy\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        mydict=defaultdict()\n",
    "        mydict2=defaultdict()\n",
    "\n",
    "        h1=head\n",
    "        i=0\n",
    "        thead=Node(0)\n",
    "        t=thead\n",
    "        while(head):\n",
    "            mydict[head]=i\n",
    "            t.next=Node(head.val)\n",
    "            mydict2[i]=t.next\n",
    "            t=t.next\n",
    "            head=head.next\n",
    "            i=i+1\n",
    "        \n",
    "        thead=thead.next\n",
    "        # while(thead):\n",
    "        #     print(thead.val)\n",
    "        #     thead=thead.next\n",
    "        h2=thead\n",
    "        head=h1\n",
    "        while(head):\n",
    "            if head.random:\n",
    "                v=mydict[head.random]\n",
    "                thead.random=mydict2[v]\n",
    "            head=head.next\n",
    "            thead=thead.next\n",
    "        return h2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return None\n",
    "        nw_head=Node(head.val)\n",
    "        nw_p=nw_head\n",
    "        p=head\n",
    "        mp={p:nw_p}\n",
    "\n",
    "        while p.next:\n",
    "            nw_p.next=Node(p.next.val)\n",
    "            mp[p.next]=nw_p.next\n",
    "            nw_p=nw_p.next\n",
    "            p=p.next\n",
    "            \n",
    "        p=head\n",
    "        nw_p=nw_head\n",
    "        mp[None]=None\n",
    "        while nw_p:\n",
    "            print(nw_p.val)\n",
    "            # nw_p=nw_p.next\n",
    "            if p.random:\n",
    "                nw_p.random=mp.get(p.random,None)\n",
    "            # if p.next:\n",
    "            nw_p=nw_p.next\n",
    "            p=p.next\n",
    "            # else:\n",
    "            #     p=None\n",
    "        return nw_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.map = dict()\n",
    "        \n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if head is None:\n",
    "            return head\n",
    "        if head not in self.map:\n",
    "            new = Node(head.val)\n",
    "            self.map[head] = new\n",
    "            new.next = self.copyRandomList(head.next)\n",
    "            new.random = self.copyRandomList(head.random)\n",
    "        return self.map[head]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import ctypes\n",
    "\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return None\n",
    "\n",
    "        # 第一遍，创建节点，构建map\n",
    "        id_map = dict()\n",
    "        p = head\n",
    "        q = None\n",
    "        while p is not None:\n",
    "            new_node = Node(p.val)\n",
    "            if q:\n",
    "                q.next = new_node\n",
    "            else:\n",
    "                new_head = new_node\n",
    "            id_map[id(p)] = id(new_node)\n",
    "            q = new_node\n",
    "            p = p.next\n",
    "\n",
    "        # 第二遍，复制random指向关系\n",
    "        p = head\n",
    "        q = new_head\n",
    "        while p is not None:\n",
    "            if p.random is not None:\n",
    "                q.random = ctypes.cast(id_map[id(p.random)], ctypes.py_object).value\n",
    "            else:\n",
    "                q.random = None\n",
    "            p = p.next\n",
    "            q = q.next\n",
    "\n",
    "        return new_head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "cache = {}\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head: return\n",
    "        global cache\n",
    "        copy = Node(head.val)\n",
    "        cache[head] = copy\n",
    "        tmp = copy\n",
    "        while head.next:\n",
    "            if head.next not in cache:\n",
    "                _next = cache[head.next] = Node(head.next.val)\n",
    "            else: _next = cache[head.next]\n",
    "            if head.random:\n",
    "                if head.random not in cache:\n",
    "                    _random = cache[head.random] = Node(head.random.val)\n",
    "                else: _random = cache[head.random]\n",
    "            else: _random = None\n",
    "            tmp.next = _next\n",
    "            tmp.random = _random\n",
    "            tmp = tmp.next\n",
    "            head = head.next\n",
    "        tmp.next = None\n",
    "        if head.random:\n",
    "            tmp.random = cache[head.random]\n",
    "        else: tmp.random = None\n",
    "        return copy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        import copy\n",
    "        return copy.deepcopy(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if head==None:\n",
    "            return None\n",
    "        \n",
    "        def nu(a,n):\n",
    "            \n",
    "            if n==0:\n",
    "                return a\n",
    "            else:\n",
    "                if a==None:\n",
    "                    a=a\n",
    "                else:\n",
    "                    a=a.next\n",
    "                n-=1\n",
    "                s=nu(a,n)\n",
    "                return s\n",
    "\n",
    "\n",
    "        a=head\n",
    "        li=[]\n",
    "        rd=[]\n",
    "        while a:\n",
    "            li.append(a.val)\n",
    "            if a.random==None:\n",
    "                rd.append(None)\n",
    "            else:\n",
    "                rd.append(a.random.val)\n",
    "            a=a.next\n",
    "        \n",
    "        def panduandizhi(hd,head,cs):\n",
    "            \n",
    "            if hd.random == None:\n",
    "                return None\n",
    "            if hd.random is head:\n",
    "                return cs\n",
    "            else:\n",
    "                cs+=1\n",
    "                #print(hd.random,head.next,cs)\n",
    "                cs=panduandizhi(hd,head.next,cs)\n",
    "                return cs\n",
    "        #print(panduandizhi(head.next.next.next,head,0))\n",
    "        \n",
    "        dic={li[i]:i for i in range(len(li))}\n",
    "        dic[None]=None\n",
    "        \n",
    "        rd_index=[dic[i] for i in rd]\n",
    "\n",
    "        rd_index=[]\n",
    "        pdh=head\n",
    "        while head:\n",
    "            \n",
    "            \n",
    "            rd_index.append(panduandizhi(pdh,head,0))\n",
    "            pdh=pdh.next\n",
    "            \n",
    "            if pdh==None:\n",
    "                break\n",
    "        #print(rd_index)\n",
    "\n",
    "        li=li[::-1]\n",
    "        b=Node(li[0])\n",
    "        if len(li)==1 and head.random==None:\n",
    "            return b\n",
    "        if len(li)==1 and head.random.val==li[0]:\n",
    "            b.random=b\n",
    "            return b\n",
    "        for i in li[1:]:\n",
    "            c=Node(i)\n",
    "            c.next=b\n",
    "            b=c\n",
    "        gc=c\n",
    "        def rdom(c,a,rd_index,n):\n",
    "            \n",
    "            if a !=None:\n",
    "                nonlocal gc\n",
    "                if a.random != None:                  \n",
    "                    c.random = nu(gc,rd_index[n])\n",
    "                else:\n",
    "                    c.random = None\n",
    "                n+=1\n",
    "                rdom(c.next,a.next,rd_index,n)\n",
    "            return c\n",
    "\n",
    "        c=rdom(c,head,rd_index,0)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def __init__(self): \n",
    "        self.index = dict()\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if head is None:\n",
    "            return None\n",
    "        # self.index = dict()\n",
    "        if head not in self.index:\n",
    "            cur = Node(head.val)\n",
    "            self.index[head] = cur\n",
    "            cur.next = self.copyRandomList(head.next)\n",
    "            cur.random = self.copyRandomList(head.random)\n",
    "        return self.index[head]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        def dfs(head):\n",
    "            if not head: return None\n",
    "            if head in visited:\n",
    "                return visited[head]\n",
    "            # 创建新结点\n",
    "            copy = Node(head.val, None, None)\n",
    "            visited[head] = copy\n",
    "            copy.next = dfs(head.next)\n",
    "            copy.random = dfs(head.random)\n",
    "            return copy\n",
    "        visited = {}\n",
    "        return dfs(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "\n",
    "        # 直接copy\n",
    "        return copy.deepcopy(head)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def __init__(self, ):\n",
    "        self.cache = {}\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        # 递归\n",
    "        if not head:\n",
    "            return \n",
    "        if head not in self.cache:\n",
    "            new_head = Node(head.val)\n",
    "            self.cache[head] = new_head \n",
    "            new_head.next = self.copyRandomList(head.next)\n",
    "            new_head.random = self.copyRandomList(head.random)\n",
    "        return self.cache[head]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not head:\n",
    "        #     return None\n",
    "        # node = head\n",
    "        # while node:\n",
    "        #     new_node = Node(node.val)\n",
    "        #     new_node.next = node.next\n",
    "        #     node.next = new_node\n",
    "        #     node = node.next.next\n",
    "        # node = head\n",
    "        # while node:\n",
    "        #     new_node = node.next\n",
    "        #     # Need detect here, because new node is next node of original node\n",
    "        #     if node.random:\n",
    "        #         new_node.random = node.random.next\n",
    "        #     node = node.next.next\n",
    "        # new_head = head.next\n",
    "        # node = head\n",
    "        # while node:\n",
    "        #     new_node = node.next\n",
    "        #     node.next = new_node.next\n",
    "        #     new_node.next = new_node.next.next if new_node.next else None\n",
    "        #     node = node.next\n",
    "        # return new_head\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    # def __init__(self,):\n",
    "    #     self.cache = {}\n",
    "\n",
    "    # def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "    #     if not head:\n",
    "    #         return None\n",
    "    #     if head not in self.cache:\n",
    "    #         new_head = Node(head.val)\n",
    "    #         self.cache[head] = new_head\n",
    "    #         new_head.next = self.copyRandomList(head.next)\n",
    "    #         new_head.random = self.copyRandomList(head.random)\n",
    "    #     return self.cache[head]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        headmap = {}\n",
    "        return self.copyList(head, headmap)\n",
    "\n",
    "    def copyList(self, head, head_map):\n",
    "        if head == None:\n",
    "            return\n",
    "        if head not in head_map:\n",
    "            new_head = Node(head.val)\n",
    "            head_map[head] = new_head\n",
    "            new_head.next = self.copyList(head.next, head_map)\n",
    "            new_head.random = self.copyList(head.random, head_map)\n",
    "\n",
    "        return head_map[head]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        visited = {}\n",
    "        def dfs_node(head):\n",
    "            if not head:\n",
    "                return None\n",
    "            if head in visited:\n",
    "                return visited[head]\n",
    "            p = head.val\n",
    "            new_head = Node(p)\n",
    "            visited[head] = new_head\n",
    "            new_head.next = dfs_node(head.next)\n",
    "            new_head.random = dfs_node(head.random)\n",
    "            return new_head\n",
    "        return dfs_node(head)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "import copy\n",
    "class Solution:\n",
    "    def _copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        return copy.deepcopy(head)\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        def dfs(head):\n",
    "            if not head: return None\n",
    "            if head in visited:\n",
    "                return visited[head]\n",
    "            # new node\n",
    "            copy = Node(head.val,None,None)\n",
    "            visited[head] = copy\n",
    "            copy.next = dfs(head.next)\n",
    "            copy.random = dfs(head.random)\n",
    "            return copy\n",
    "        visited = {}\n",
    "        return dfs(head)\n",
    "\n",
    "        def bfs(head):\n",
    "            if not head: return head\n",
    "            copy = Node(head.val,None,None)\n",
    "            queue = collections.deque()\n",
    "            queue.append(head)\n",
    "            visited[head] = copy\n",
    "            while queue:\n",
    "                tmp = queue.pop()\n",
    "                if tmp.next and tmp.next not in visited:\n",
    "                    visited[tmp.next] = Node(tmp.next.val,None,None)\n",
    "                    queue.append(tmp.next)\n",
    "                if tmp.random and tmp.random not in visited:\n",
    "                    visited[tmp.random] = Node(tmp.random.val,None,None)\n",
    "                    queue.append(tmp.random)\n",
    "                visited[tmp].next = visited.get(tmp.next)\n",
    "                visited[tmp].random = visited.get(tmp.random)\n",
    "            return clone\n",
    "        #return bfs(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        def dfs(head):\n",
    "            if not head: return None\n",
    "            if head in visited:\n",
    "                return visited[head]\n",
    "            # 创建新结点\n",
    "            copy = Node(head.val, None, None)\n",
    "            visited[head] = copy\n",
    "            copy.next = dfs(head.next)\n",
    "            copy.random = dfs(head.random)\n",
    "            return copy\n",
    "        visited = {}\n",
    "        return dfs(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        visited = {}\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return node\n",
    "            if node in visited:\n",
    "                return visited[node]\n",
    "            else:\n",
    "                cur = Node(node.val, None, None)\n",
    "                visited[node] = cur\n",
    "                cur.next = dfs(node.next)\n",
    "                cur.random = dfs(node.random)\n",
    "                return cur\n",
    "        return dfs(head)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        self.arrived={}\n",
    "\n",
    "\n",
    "        node=self.traverse(head)\n",
    "        return node\n",
    "    def traverse(self,head):\n",
    "        if head in self.arrived:\n",
    "            return self.arrived[head]\n",
    "        if not head:\n",
    "            return\n",
    "        val=head.val\n",
    "        newNode=Node(val)\n",
    "\n",
    "\n",
    "        self.arrived[head]=newNode\n",
    "        newNode.next=self.traverse(head.next)\n",
    "\n",
    "        newNode.random=self.traverse(head.random)\n",
    "\n",
    "        return newNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.map = {}\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if head is None:\n",
    "            return head\n",
    "        if head in self.map:\n",
    "            return self.map[head]\n",
    "        new_head = Node(head.val)\n",
    "        self.map[head] = new_head\n",
    "        new_head.next = self.copyRandomList(head.next)\n",
    "        new_head.random = self.copyRandomList(head.random)\n",
    "        \n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.cached = dict()\n",
    "\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return None\n",
    "        if head not in self.cached:\n",
    "            new = Node(head.val)\n",
    "            self.cached[head] = new\n",
    "            new.next = self.copyRandomList(head.next)\n",
    "            new.random = self.copyRandomList(head.random)\n",
    "        return self.cached[head]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        def dfs(head):\n",
    "            if not head: return None\n",
    "            if head in visited:\n",
    "                return visited[head]\n",
    "            # 创建新结点\n",
    "            copy = Node(head.val, None, None)\n",
    "            visited[head] = copy\n",
    "            copy.next = dfs(head.next)\n",
    "            copy.random = dfs(head.random)\n",
    "            return copy\n",
    "        visited = {}\n",
    "        return dfs(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        vistied = {}\n",
    "        def copyNode(onode):\n",
    "            if not onode: return None\n",
    "            node = Node(onode.val)\n",
    "            vistied[id(onode)] = node\n",
    "            if onode.next:\n",
    "                if id(onode.next) not in vistied.keys():\n",
    "                    node.next = copyNode(onode.next)\n",
    "                else: node.next = vistied[id(onode.next)]\n",
    "            if onode.random:\n",
    "                if id(onode.random) not in vistied.keys():\n",
    "                    node.random = copyNode(onode.random)\n",
    "                else: node.random = vistied[id(onode.random)]\n",
    "            return node\n",
    "        \n",
    "        return copyNode(head)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        ans={\n",
    "            head:Node(head.val)\n",
    "        }\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            if root.next:\n",
    "                if root.next not in ans:\n",
    "                    ans[root.next]=Node(root.next.val)\n",
    "                    ans[root].next=ans[root.next]\n",
    "                    dfs(root.next)\n",
    "\n",
    "\n",
    "            if root.random:\n",
    "                if root.random not in ans:\n",
    "                    ans[root.random]=Node(root.random.val)\n",
    "                ans[root].random=ans[root.random]\n",
    "\n",
    "\n",
    "        dfs(head)\n",
    "        return ans[head]                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        def dfs(head):\n",
    "            if not head: return None\n",
    "            if head in visited:\n",
    "                return visited[head]\n",
    "            # 创建新结点\n",
    "            copy = Node(head.val, None, None)\n",
    "            visited[head] = copy\n",
    "            copy.next = dfs(head.next)\n",
    "            copy.random = dfs(head.random)\n",
    "            return copy\n",
    "        visited = {}\n",
    "        return dfs(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        # copyhead = Node(x=head.val,next=head.next,random=head.random)\n",
    "        # 创建所有节点\n",
    "        # 按照next、random重新连接:next可以按照顺序复制，那random如何复制呢？ 字典！！\n",
    "        # 如：递归的创建节点\n",
    "        if not head: return\n",
    "\n",
    "        # cpList = {}\n",
    "        # cur = head\n",
    "        # # print(cur,head)\n",
    "        # while cur:\n",
    "        #     cpList[cur]=Node(cur.val,None,None)\n",
    "        #     cur = cur.next\n",
    "\n",
    "        # for k,v in cpList.items():\n",
    "        #     if k.next:\n",
    "        #         v.next = cpList[k.next] # next\n",
    "        #     if k.random:\n",
    "        #         v.random = cpList[k.random] # random\n",
    "        # # print(cur,head)\n",
    "        # return cpList[head]\n",
    "            \n",
    "        cplist = {head:Node(head.val,None,None)}\n",
    "        def createNode(head,cplist):\n",
    "            # 如何检查node是否已经创建？字典！！\n",
    "            if not head: return\n",
    "            \n",
    "            cphead = cplist[head]\n",
    "\n",
    "            if head.next:\n",
    "                if head.next not in cplist:\n",
    "                    cphead.next = Node(head.next.val,None,None)\n",
    "                    cplist[head.next] = cphead.next # 映射\n",
    "                    createNode(head.next,cplist)\n",
    "                else: \n",
    "                    cphead.next = cplist[head.next]\n",
    "\n",
    "\n",
    "            if head.random:\n",
    "                cphead.random = cplist[head.random]\n",
    "                print(cplist[head.random])\n",
    "\n",
    "                \n",
    "        createNode(head,cplist)\n",
    "\n",
    "        # for k, v in cplist.items():\n",
    "        #     print(v.val,v.next,v.random)\n",
    "\n",
    "        return cplist[head]\n",
    "        # print(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        def dfs(head):\n",
    "            if not head: return None\n",
    "            if head in visited:\n",
    "                return visited[head]\n",
    "            # 创建新结点\n",
    "            copy = Node(head.val, None, None)\n",
    "            visited[head] = copy\n",
    "            copy.next = dfs(head.next)\n",
    "            copy.random = dfs(head.random)\n",
    "            return copy\n",
    "        visited = {}\n",
    "        return dfs(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def backtracking(self, node):\n",
    "        if not node: \n",
    "            return\n",
    "        if node not in self.node_set:\n",
    "            new_node = Node(node.val)\n",
    "            self.node_set[node] = new_node\n",
    "            next_ = self.backtracking(node.next)\n",
    "            random = self.backtracking(node.random)\n",
    "            new_node.next = next_\n",
    "            new_node.random = random\n",
    "        return self.node_set[node]\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        self.node_set = {}\n",
    "        return self.backtracking(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    mp = {}\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return None\n",
    "        if head in self.mp:\n",
    "            return self.mp[head]\n",
    "        copy = Node(head.val)\n",
    "        self.mp[head] = copy\n",
    "        copy.next = self.copyRandomList(head.next)\n",
    "        copy.random = self.copyRandomList(head.random)\n",
    "        return copy\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def __init__(self,):\n",
    "        self.cache = {}\n",
    "\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return None\n",
    "        if head not in self.cache:\n",
    "            new_head = Node(head.val)\n",
    "            self.cache[head] = new_head\n",
    "            new_head.next = self.copyRandomList(head.next)\n",
    "            new_head.random = self.copyRandomList(head.random)\n",
    "        return self.cache[head]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.cachedNode = dict()\n",
    "\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if head is None:\n",
    "            return None\n",
    "        if head in self.cachedNode:\n",
    "            return self.cachedNode[head]\n",
    "\n",
    "        headNew = Node(head.val)\n",
    "        self.cachedNode[head] = headNew\n",
    "        \n",
    "        headNew.next = self.copyRandomList(head.next)\n",
    "        headNew.random = self.copyRandomList(head.random)\n",
    "        \n",
    "        return headNew\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        node_table = {}\n",
    "        def copy_list(cur):\n",
    "            if(not cur):\n",
    "                return None\n",
    "            if cur in node_table:\n",
    "                return node_table[cur]\n",
    "            newnode = Node(cur.val, None, None)\n",
    "            node_table[cur] = newnode\n",
    "            newnode.next = copy_list(cur.next)\n",
    "            newnode.random = copy_list(cur.random)\n",
    "            return newnode\n",
    "        return copy_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "mm={}\n",
    "class Solution:\n",
    "   \n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head in mm:\n",
    "            node = Node(head.val)\n",
    "            mm[head]=node\n",
    "            node.next=self.copyRandomList(head.next)\n",
    "            node.random=self.copyRandomList(head.random)\n",
    "        return mm[head]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        visited = {}\n",
    "        \n",
    "        def dfs(head):\n",
    "            if not head:\n",
    "                return\n",
    "            if head in visited:\n",
    "                return visited[head]\n",
    "\n",
    "            copy = Node(head.val)\n",
    "            visited[head] = copy\n",
    "            \n",
    "            copy.next = dfs(head.next)\n",
    "            copy.random = dfs(head.random)\n",
    "\n",
    "            return copy\n",
    "\n",
    "        return dfs(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    memo = {}\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        if head not in self.memo:\n",
    "            cur = Node(head.val)\n",
    "            self.memo[head] = cur\n",
    "            cur.next = self.copyRandomList(head.next)\n",
    "            cur.random = self.copyRandomList(head.random)\n",
    "        return self.memo[head]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "\n",
    "        searched={}\n",
    "        def search(node=head):\n",
    "            if node in searched:\n",
    "                return searched[node]\n",
    "\n",
    "            if node :\n",
    "                node_copy=Node(\n",
    "                    x=node.val,\n",
    "                    )\n",
    "                searched[node]=node_copy\n",
    "                node_copy.next=search(node.next)\n",
    "                node_copy.random=search(node.random)\n",
    "            else:\n",
    "                node_copy=None\n",
    "            \n",
    "            \n",
    "            return node_copy\n",
    "        \n",
    "        return search()\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        def dfs(head):\n",
    "            if not head: return None\n",
    "            if head in visited:\n",
    "                return visited[head]\n",
    "            # 创建新结点\n",
    "            copy = Node(head.val, None, None)\n",
    "            visited[head] = copy\n",
    "            copy.next = dfs(head.next)\n",
    "            copy.random = dfs(head.random)\n",
    "            return copy\n",
    "        visited = {}\n",
    "        return dfs(head)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        return copy.deepcopy(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        self.used={}\n",
    "        return self.traver(head)\n",
    "    def traver(self,head):\n",
    "        if not head:\n",
    "            return None\n",
    "        if head in self.used:\n",
    "            return self.used[head]\n",
    "\n",
    "\n",
    "        print(head.val)\n",
    "        newNode=Node(head.val)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        self.used[head]=newNode\n",
    "        newNode.next=self.traver(head.next)\n",
    "\n",
    "        \n",
    "\n",
    "        newNode.random=self.traver(head.random)\n",
    "\n",
    "        return newNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        return copy.deepcopy(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Node') -> 'Node':\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        self.used={}\n",
    "        return self.traver(head)\n",
    "    def traver(self,head):\n",
    "        if not head:\n",
    "            return None\n",
    "        if head in self.used:\n",
    "            return self.used[head]\n",
    "\n",
    "\n",
    "        print(head.val)\n",
    "        newNode=Node(head.val)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        self.used[head]=newNode\n",
    "        newNode.next=self.traver(head.next)\n",
    "\n",
    "        \n",
    "\n",
    "        newNode.random=self.traver(head.random)\n",
    "\n",
    "        return newNode"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
